package leetcode.graph;


import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 841. 钥匙和房间
 *
 */
public class CanVisitAllRooms {

    // 访问标识数组
    boolean[] vis;
    // 计数器
    int num;

    /**
     * DFS 深度优先遍历
     *
     * @param rooms 所有房间的钥匙
     * @return
     */
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        // 打开的房间数量
        num = 0;
        // 当前房间是否打开过
        vis = new boolean[n];

        // 从0号房间开始进入, 一开始0号房间是打开的
        dfs(rooms, 0);
        return num == n;
    }


    /**
     * 递归方法
     *
     * 方法意义
     *      进入当前房间, 并且使用房间内的钥匙打开其他的房间
     *
     * @param rooms     所有房间的钥匙
     * @param x         当前房间号码
     */
    public void dfs(List<List<Integer>> rooms, int x) {
        // 标记当前房间已经打开了
        vis[x] = true;

        // 打开的房间数加1
        num++;

        // 当前房间可以获得的钥匙集合
        for (int it : rooms.get(x)) {
            // 如果这个钥匙对应的房间已经打开过, 就不需要再次进入了
            if (!vis[it]) {
                // 使用房间里的钥匙, 递归进入对应的房间
                dfs(rooms, it);
            }
        }
    }


    /**
     * BFS 广度优先遍历
     *
     * @param rooms 所有房间
     * @return
     */
    public boolean canVisitAllRooms2(List<List<Integer>> rooms) {
        int n = rooms.size(), num = 0;
        // 访问标识数组
        boolean[] vis = new boolean[n];
        // 队列
        Queue<Integer> que = new LinkedList<>();

        // 访问第一个节点并且入队
        vis[0] = true;
        que.offer(0);
        while (!que.isEmpty()) {
            // 取出队头元素
            int x = que.poll();

            // 计算器加1
            num++;
            for (int it : rooms.get(x)) {
                // 遍历所有未访问过的相邻节点
                if (!vis[it]) {
                    vis[it] = true;
                    // 相邻节点入队
                    que.offer(it);
                }
            }
        }
        return num == n;
    }

}
